package com.nanbei.backyracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @ClassDescription:  (回溯算法)给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。 leetCode 47
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/12 14:37
 */
public class PermutationsIi {
    public static void main(String[] args) {
        List<List<Integer>> permute = permuteUnique(new int[]{1,3, 1});
        System.out.println(permute.size());
        System.out.println(permute);
    }

    public static List<List<Integer>> permuteUnique(int[] nums) {
        // 用来判断是否访问标识
        boolean[] visited = new boolean[nums.length];
        // 用来存放背访问的字符串
        LinkedList<Integer> stack = new LinkedList<>();
        //  用来存放所有的排列结果
        List<List<Integer>> target = new ArrayList<>();
        Arrays.sort(nums);
        huiShu(nums,visited,stack,target);
        return target;
    }

    private static void huiShu(int[] nums, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> target) {

        // 当栈中的元素数量等于数组长度时，表示找到了一种排列
        if (stack.size() == nums.length){
            target.add(new ArrayList<>(stack));
            return ;
        }

        for (int i = 0; i < nums.length; i++) {
            // 去重：跳过重复的数字
            // 如果存在两个重复的数字，必须先确定第一个数字的位置，如果第一个数字的位置没有被确定则跳过当前数字
            if (i>0 && nums[i] == nums[i-1] && !visited[i-1]){
                continue;
            }

            // 判断当前数字是否被访问过
            if(!visited[i]){
                // 如果没有访问过则进行排列
                // 设置当前数字的访问标识为true代表已经访问过了
                visited[i] = true;
                // 将该数字加入栈中
                stack.push(nums[i]);
                // 递归调用后面的数字
                huiShu(nums, visited, stack, target);
                // 回溯：将该数字移出栈，并将访问标识设为false
                stack.pop();
                visited[i] = false;
            }
        }

    }
}
